# -*- coding: utf-8 -*-

"""剑指 Offer II 063. 替换单词
在英语中，有一个叫做 词根(root) 的概念，它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。
现在，给定一个由许多词根组成的词典和一个句子，需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。
需要输出替换之后的句子。

示例 1：
输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
输出："the cat was rat by the bat"

示例 2：
输入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
输出："a a b c"

示例 3：
输入：dictionary = ["a", "aa", "aaa", "aaaa"], sentence = "a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa"
输出："a a a a a a a a bbb baba a"

示例 4：
输入：dictionary = ["catt","cat","bat","rat"], sentence = "the cattle was rattled by the battery"
输出："the cat was rat by the bat"

示例 5：
输入：dictionary = ["ac","ab"], sentence = "it is abnormal that this solution is accepted"
输出："it is ab that this solution is ac"

提示：
1 <= dictionary.length <= 1000
1 <= dictionary[i].length <= 100
dictionary[i] 仅由小写字母组成。
1 <= sentence.length <= 10^6
sentence 仅由小写字母和空格组成。
sentence 中单词的总量在范围 [1, 1000] 内。
sentence 中每个单词的长度在范围 [1, 1000] 内。
sentence 中单词之间由一个空格隔开。
sentence 没有前导或尾随空格。"""


class TrieNode():
    def __init__(self) -> None:
        self.children = [None]*26
        self.isEnd = False


def pretty_show(trieNode):
    stack = []
    def recursion(node):
        if node.isEnd:
            print(stack)
        childs = [(chr(idx+97), cnode) for idx, cnode in zip(range(26), node.children) if cnode]
        for ch, cnode in childs:
            stack.append(ch)
            recursion(cnode)
            stack.pop()
    recursion(trieNode)


class Solution:
    def replaceWords(self, dictionary, sentence: str) -> str:
        # 构建前缀树
        trie = TrieNode()
        for word in dictionary:
            node = trie
            for ch in word:
                idx = ord(ch)-97
                if not node.children[idx]:
                    node.children[idx] = TrieNode()    
                node = node.children[idx]
            node.isEnd = True
        
        sentence += ' '
        cursor, hi, new_sentence = 0, len(sentence)-1, ''
        while cursor <= hi:
            # 开始一个单词的查询
            head, node, stack = cursor, trie, []
            while True:
                if node.isEnd:
                    break
                ch = sentence[cursor]
                idx = ord(ch)-97
                if idx >= 0 and node.children[idx]:
                    stack.append(ch)
                    node = node.children[idx]
                    cursor += 1
                else:
                    stack.clear()
                    break

            # 游标移动到一个单词结束
            while True:
                if sentence[cursor] == ' ':
                    break
                cursor += 1
            
            if stack:
                new_sentence += ''.join(stack)
            else:
                new_sentence += sentence[head:cursor]
            
            new_sentence += ' '
            cursor += 1

        return new_sentence[0:-1]


if __name__ == '__main__':
    so = Solution()
    # print(so.replaceWords(dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"))
    # print(so.replaceWords(dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"))
    # print(so.replaceWords(dictionary = ["a", "aa", "aaa", "aaaa"], sentence = "a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa"))
    # print(so.replaceWords(dictionary = ["catt","cat","bat","rat"], sentence = "the cattle was rattled by the battery"))
    # print(so.replaceWords(dictionary = ["ac","ab"], sentence = "it is abnormal that this solution is accepted"))
    print(so.replaceWords(dictionary = ["e","k","c","harqp","h","gsafc","vn","lqp","soy","mr","x","iitgm","sb","oo","spj","gwmly","iu","z","f","ha","vds","v","vpx","fir","t","xo","apifm","tlznm","kkv","nxyud","j","qp","omn","zoxp","mutu","i","nxth","dwuer","sadl","pv","w","mding","mubem","xsmwc","vl","farov","twfmq","ljhmr","q","bbzs","kd","kwc","a","buq","sm","yi","nypa","xwz","si","amqx","iy","eb","qvgt","twy","rf","dc","utt","mxjfu","hm","trz","lzh","lref","qbx","fmemr","gil","go","qggh","uud","trnhf","gels","dfdq","qzkx","qxw"],
                          sentence = "ikkbp miszkays wqjferqoxjwvbieyk gvcfldkiavww vhokchxz dvypwyb bxahfzcfanteibiltins ueebf lqhflvwxksi dco kddxmckhvqifbuzkhstp wc ytzzlm gximjuhzfdjuamhsu gdkbmhpnvy ifvifheoxqlbosfww mengfdydekwttkhbzenk wjhmmyltmeufqvcpcxg hthcuovils ldipovluo aiprogn nusquzpmnogtjkklfhta klxvvlvyh nxzgnrveghc mpppfhzjkbucv cqcft uwmahhqradjtf iaaasabqqzmbcig zcpvpyypsmodtoiif qjuiqtfhzcpnmtk yzfragcextvx ivnvgkaqs iplazv jurtsyh gzixfeugj rnukjgtjpim hscyhgoru aledyrmzwhsz xbahcwfwm hzd ygelddphxnbh rvjxtlqfnlmwdoezh zawfkko iwhkcddxgpqtdrjrcv bbfj mhs nenrqfkbf spfpazr wrkjiwyf cw dtd cqibzmuuhukwylrnld dtaxhddidfwqs bgnnoxgyynol hg dijhrrpnwjlju muzzrrsypzgwvblf zbugltrnyzbg hktdviastoireyiqf qvufxgcixvhrjqtna ipfzhuvgo daee r nlipyfszvxlwqw yoq dewpgtcrzausqwhh qzsaobsghgm ichlpsjlsrwzhbyfhm ksenb bqprarpgnyemzwifqzz oai pnqottd nygesjtlpala qmxixtooxtbrzyorn gyvukjpc s mxhlkdaycskj uvwmerplaibeknltuvd ocnn frotscysdyclrc ckcttaceuuxzcghw pxbd oklwhcppuziixpvihihp"))
